package doublePtr

func sortColors(nums []int) {
	// 用两个指针p和q分别指向0应该插入的位置和2应该插入的位置
	// 遍历整个slice，遇到0移动到p处，遇到2移到q处，判断条件为i < q，遇到1不处理
	// 但是如果交换后i位置的数字不为1，那么需要将i减一，然后进入下一次循环后i又自增1，就又会回到上一次交换的位置，对0或2进行处理
	p, q := 0, len(nums)-1
	// 为什么这里要使用i<=q, 假设q为x，则q--后为x-1, 那么此时nums[x-1]可能还没有进行过交换，所以为i <= q
	for i := 0; i <= q; i++ {
		// 遇到0插入到p
		if nums[i] == 0 {
			nums[p], nums[i] = nums[i], nums[p]
			p++
		}
		if nums[i] == 2 {
			nums[q], nums[i] = nums[i], nums[q]
			q--
			// 这一步必须放if nums[i] == 2里面
			// 因为如果放外面，则当p处为0，nums[i]处也为0时，每次交换p往右移动，但是交换后i处还是0，所以i会先减去1，下次循环自增1
			// 相当于i不变，一直在原地踏步，而此时p可能已经在i的右边了，再继续交换就会导致错误
			if nums[i] != 1 {
				i--
			}
		}
	}
}
